#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
#include<set>

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> result;
        if(matrix.size()==0){
            return result;
        }
        set<pair<int,int>> S;
        func(matrix,0,0,matrix.size()-1,matrix[0].size()-1,result,S);
        return result;
    }
    void func(vector<vector<int>>& matrix,int startrow,int startcolumn,int endrow,int endcolumn,vector<int>& result,set<pair<int,int>>& S){
        if(startrow>endrow||startcolumn>endcolumn){
            return;
        }
        for(int i = startcolumn;i<=endcolumn;++i){
            if(S.insert(make_pair(startrow,i)).second){
                result.push_back(matrix[startrow][i]);
            }
        }
        for(int i = startrow;i<=endrow;++i){
            if(S.insert(make_pair(i,endcolumn)).second){
                result.push_back(matrix[i][endcolumn]);
            }
        }
        for(int i =endcolumn;i>=startcolumn;--i){
            if(S.insert(make_pair(endrow,i)).second){
                result.push_back(matrix[endrow][i]);
            }
        }
        for(int i = endrow;i>=startrow;--i){
            if(S.insert(make_pair(i,startcolumn)).second){
                result.push_back(matrix[i][startcolumn]);
            }
        }
        func(matrix,startrow+1,startcolumn+1,endrow-1,endcolumn-1,result,S);
        return;
    }
};

int main(){
    vector<vector<int>> matrix = {{1,2,3,4},{5,6,7,8},{9,10,11,12}};
    Solution S;
    vector<int> result = S.spiralOrder(matrix);
    return 0;
}